package personal.leil.learning.exercises;

import personal.leil.learning.SNode;
import personal.leil.learning.utils.LinkedListUtils;

/**
 * 将一个链表基于一个数partition，并保持稳定性
 * <p>
 * 额外空间复杂度O(1)
 * </p>
 */
public class Question3 {

    public static SNode process(SNode head, int num) {
        SNode ltS = null, ltE = null,
                eqS = null, eqE = null,
                gtS = null, gtE = null;
        SNode current = head;
        while (current != null) {
            SNode next = current.getNext();
            current.setNext(null);
            int val = (int) current.getData();
            if (val < num) {
                if (ltS == null) {
                    ltS = current;
                } else {
                    ltE.setNext(current);
                }
                ltE = current;
            } else if (val > num) {
                if (gtS == null) {
                    gtS = current;
                } else {
                    gtE.setNext(current);
                }
                gtE = current;
            } else {
                if (eqS == null) {
                    eqS = current;
                } else {
                    eqE.setNext(current);
                }
                eqE = current;
            }
            current = next;
        }
        if (ltS != null && eqS != null && gtS != null) {
            ltE.setNext(eqS);
            eqE.setNext(gtS);
            return ltS;
        } else if (ltS != null && eqS != null) {
            ltE.setNext(eqS);
            return ltS;
        } else if (ltS != null && gtS != null) {
            ltE.setNext(gtS);
            return ltS;
        } else if (eqS != null && gtS != null) {
            eqE.setNext(gtS);
            return eqS;
        } else if (ltS != null) {
            return ltS;
        } else if (eqS != null) {
            return eqS;
        } else if (gtS != null) {
            return gtS;
        }
        return head;
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        SNode head = LinkedListUtils.buildSingleLinkedList(new int[]{5, 4, 2, 6, 8, 9, 10, 22, 11});
//        LinkedListUtils.printSingleLinkedList(head);
//        SNode head1 = process(head, 22);
//        System.out.println("after process:" + 22);
//        LinkedListUtils.printSingleLinkedList(head1);

//        LinkedListUtils.printSingleLinkedList(head);
//        SNode head2 = process(head, 13);
//        System.out.println("after process:" + 13);
//        LinkedListUtils.printSingleLinkedList(head2);


//        LinkedListUtils.printSingleLinkedList(head);
//        SNode head3 = process(head, 5);
//        System.out.println("after process:" + 5);
//        LinkedListUtils.printSingleLinkedList(head3);


        LinkedListUtils.printSingleLinkedList(head);
        SNode head4 = process(head, 1);
        System.out.println("after process:" + 1);
        LinkedListUtils.printSingleLinkedList(head4);
    }


}
